Number of Digit One || Integer Replacement

发表于

Number of Digit One

Question

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:

Given n = 13,

Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Analysis

每10个数, 有一个个位是1, 每100个数, 有10个十位是1, 每1000个数, 有100个百位是1. 做一个循环, 每次计算单个位上1得总个数(个位,十位, 百位).

例子:

以算百位上1为例子: 假设百位上是0, 1, 和 >=2 三种情况: 

case 1: n=3141092, a= 31410, b=92. 计算百位上1的个数应该为 3141 *100 次.

case 2: n=3141192, a= 31411, b=92. 计算百位上1的个数应该为 3141 *100 + (92+1) 次. 

case 3: n=3141592, a= 31415, b=92. 计算百位上1的个数应该为 (3141+1) *100 次.

以上三种情况可以用 一个公式概括:

(a + 8) / 10 m + (a % 10 == 1) (b + 1);

考虑到m可能会导致overflow，a,b,m均用long型

Code

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int countDigitOne(int n) {
        int ones=0;
        for(long m=1;m<=n;m*=10){
            long a=n/m,b=n%m;
            ones+=(a+8)/10*m;
            if(a%10==1) ones+=b+1;
        }
        return ones;
    }
}

Integer Replacement

Question

Given a positive integer n and you can do operations as follow:

  1. If n is even, replace n with n/2.
  2. If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

1
2
3
4
5
6
7
8
Input:
8
Output:
3
Explanation:
8 -> 4 -> 2 -> 1

Example 2:

1
2
3
4
5
6
7
8
9
10
Input:
7
Output:
4
Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

Analysis

LeetCode Discussion

判断多少次操作后可以变1，显然应该通过位操作，分为两种情况，偶数/奇数

  1. 偶数

    偶数只需数字n无符号右移1位即可，注意判断的时候可以通过&1判断是否为偶数

  2. 奇数

    通过以下示例可知，应该尽量将二进制n中的1的个数变少，有两种方法

    • 利用Integer.bitCount() 统计n+1与n-1后二进制数内1的个数，取少的那种做法
    • 只需判断后两位数字即可，由于此时数为奇数，故末尾数一定为1
      • 假如倒数第二位数字为1，即11，此时+1操作所得数含1个数不多于-1操作，100/010
      • 假如倒数第二位数字为0，即01，此时显然-1操作优于+1操作

    操作一：

    1
    111011 -> 111010 -> 11101 -> 11100 -> 1110 -> 111 -> 1000 -> 100 -> 10 -> 1

    操作二：

    1
    111011 -> 111100 -> 11110 -> 1111 -> 10000 -> 1000 -> 100 -> 10 -> 1

    操作二的次数显然少于操作一

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int integerReplacement(int n) {
        int cnt=0;
        while(n!=1){
            if((n&1)==0)
                n>>>=1;
            else{
                if(n==3||((n>>>1)&1)==0)
                    n--;
                else 
                    n++;
            }
            cnt++;
        }
        return cnt;
    }
}